#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
题⽬链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs/
数组的每个下标作为⼀个阶梯，第 i 个阶梯对应着⼀个⾮负数的体⼒花费值 cost[i]（下标从 0 开始）。
每当你爬上⼀个阶梯你都要花费对应的体⼒值，⼀旦⽀付了相应的体⼒值，你就可以选择向上爬⼀个阶
梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输⼊：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后⾛两步即可到阶梯顶，⼀共花费 15 。
示例 2：输⼊：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费⽅式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，⼀共花费 6 。
提示：
cost 的⻓度范围是 [2, 1000]。
cost[i] 将会是⼀个整型数据，范围为 [0, 999] 。
 * */
//1定义 dp[i] i是特定的台阶 dp[i]上到i台阶最少花费的体力值
//2确定递推公式 公式不一定是+ 什么的 也许是min max  可以有两个途径得到dp[i]，⼀个是dp[i-1] ⼀个是dp[i-2] dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
//3. dp数组如何初始化 直接dp[0] 对应arr[0] dp[1] 对应arr[1];
//4 遍历顺序从前向后
int minCostClimbingStairs(vector<int> &cost) {
    vector<int> dp(cost.size());

    //
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < cost.size(); ++i) {
        dp[i] = min(dp[i - 2], dp[i - 1]) + cost[i];
    }


    return min(dp[cost.size() - 1], dp[cost.size() - 2]);
}